package com.example.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 数组最大异或
 */
public class Demo0421 {
    private static final int HIGH_BIT=30;

    public static void main(String[] args) {
        System.out.println(6^6);
        System.out.println(maxOr2(new Integer[]{-2147483648,8,2,5,25,56}));
    }

    /**
     * 暴力解法
     * @param arr
     * @return
     */
    public static Integer maxOr1(Integer [] arr){
        Integer res=0;
        if (arr.length==1){
            return 0;
        }else {
            for (int i = 0; i < arr.length-1; i++) {
                for (int j =i+1; j < arr.length; j++) {
                   res= (arr[i]^arr[j])>res?arr[i]^arr[j]:res;
                }
            }
        }
        return res;
    }

    /**
     * 哈希表解法
     * @param arr
     * @return
     */
    public static Integer maxOr2(Integer [] arr){
        int res=0;
        for (int k = HIGH_BIT; k >= 0; k--) {
            Set<Integer> seen=new HashSet<>();
            for (Integer num : seen) {
                seen.add(num>>k);
            }

            int rK=res*2+1;//此步骤假设这一位为1
            boolean flag=false;//此步骤假设上句话为假
            for (Integer num : seen) {
                if (seen.contains(rK^(num>>2))){
                    flag=true;
                    break;
                }
            }
            if (flag){
                res=rK;
            }else {
                res=rK-1;
            }
        }

        return res;
        /*int res=0;
        for (int k = HIGH_BIT; k >=0; k--) {
            Set<Integer> seen = new HashSet<>();
            for (Integer num : arr) {
                seen.add(num>>k);
            }

            int xNext=res*2+1;
            boolean found=false;
            for (Integer num : arr) {
                if (seen.contains(xNext^(num>>k))){
                    found=true;
                    break;
                }
            }
            if (found){
                res=xNext;
            }else {
                res=xNext-1;
            }
        }
        return res;*/
    }
}
